package com.origin.niuke.greedy;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * NC175 合法的括号字符串
 * 算法：贪心、栈
 * 栈：
 * 定义两个栈, 一个栈存储 '(' 的下标, 另一个栈存储 '*' 的下标
 * 遍历到 '(' 和 '*', 则将下标放到各自的栈中,
 * 如果遍历到 ')', 先判断 '(' 栈是否有元素, 如果有, 则将栈顶元素出栈;
 * 反之, 判断 '*' 栈是否有元素, 如果没有, 直接返回 false; 反之, 将栈顶元素弹出
 * 遍历完后, 判断 '(' 栈中是否还存在元素
 * 如果有, 则遍历栈, 如果 '*' 栈没有元素, 直接返回 false;
 * 反之, 比较 '(' 栈和 '*' 栈的栈顶元素的大小, 如果前者的大, 则返回 false
 * 否则继续遍历, 直到 '(' 栈为空为止
 * 贪心:
 * 定义两个变量存储最小 '(' 和最大 '(' 的个数, minLeft, maxLeft
 * 如果遍历到 '(', 则两个变量都 +1
 * 如果遍历到 '*', minLeft - 1, maxLeft + 1
 * 如果遍历到 ')', if (minLeft > 0) --minLeft, if (maxLeft < 0) return false, --maxLeft
 *
 * @author yezh
 * @date 2023/1/5 21:05
 */
public class NC175 {

    public boolean isValidString(String s) {
        int minLeft = 0, maxLeft = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ')') {
                if (maxLeft == 0) return false;
                if (minLeft > 0) --minLeft;
                --maxLeft;
            } else {
                if (c == '(') ++minLeft;
                else if (minLeft > 0) --minLeft;
                ++maxLeft;
            }
        }
        return minLeft == 0;
    }

    public boolean isValidString_stack(String s) {
        // write code here
        Deque<Integer> left = new ArrayDeque<>();
        Deque<Integer> star = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ')') {
                if (!left.isEmpty()) left.pollFirst();
                else {
                    if (star.isEmpty()) return false;
                    star.pollFirst();
                }
            } else if (c == '(') left.addFirst(i);
            else star.addFirst(i);
        }
        while (!left.isEmpty()) {
            if (star.isEmpty()) return false;
            if (left.pollFirst() > star.pollFirst()) return false;
        }
        return true;
    }

}
